package cxydmmszl.chapter01.t010;

import java.util.LinkedList;

/**
 * <li style="color: red;">Prob</li>
 * 最大值减去最小值小于或等于 num 的子数组数量
 * <li style="color: red;">Desc</li>
 * 给定数组 arr 和整数 num，共返回有多少个子数组满足如下情况：<br/>
 * &emsp;max(arr[i...j]) - min(arr[i...j]) <= num<br/>
 * &emsp;max(arr[i...j])，min(arr[i...j]) 分别表示子数组 arr[i...j] 中的最大值和最小值。
 * <li style="color: red;">Link</li> CD18
 *
 * @author habitplus
 * @since 2021-08-27 14:03
 */
public class Main {
    public int numOfRangeSubArr(int[] arr, int num) {
        /* 结论：如果子数组 arr[i...j] 满足条件 max(arr[i...j]) - min(arr[i...j]) <= num，
         *      则 arr[i...j] 每一个子数组 arr[k,l](i<=l<=k<=j)都会满足条件
         * 解题思路：
         * 1. 生成两个双端队列 qmax 和 qmin。
         *    生成两个整型变量 i 和 j，表示数组的范围，即 arr[i...j]。
         *    生成整型变量 ans，表示所有满足条件的子数组数量。
         * 2. 令 j 不断向右移动（j++），表示 arr[i...j] 一直向右扩大，并不断更新 qmax 和 qmin 结构，
         *    保证 qmax 和 qmin 始终维持动态窗口最大值和最小值的更新结构。
         *    一旦出现 arr[i...j] 不满足条件的情况，j 向右扩的过程停止，
         *    此时 arr[i...j-1], arr[i...j-2], ..., arr[i...i] 一定都是满足条件的。也就是说，
         *    所有必须以 arr[i] 作为第一个元素的子数组，满足条件的数量为 j - i 个。于是令 res += (j - i)。
         * 3. 当进行完步骤 2，令 i 向右移动一个位置，并对 qmax 和 qmin 做出相应更新（主要是移除当前 i），
         *    qmax 和 qmin 从原来的 arr[i...j] 窗口变成 arr[i+1...j] 窗口的最大值和最小值的更新结构。
         *    然后重复步骤 2，也就是求所有以 arr[i+1] 作为第一个元素的子数组中，满足条件的数量有多少个。
         */
        if (arr == null || arr.length < 1 || num < 0) {
            return 0;
        }

        int ans = 0;
        int i = 0, j = 0, n = arr.length;
        // 最小值的队列
        LinkedList<Integer> qmin = new LinkedList<>();
        // 最大值的队列
        LinkedList<Integer> qmax = new LinkedList<>();

        while (i < n) {
            while (j < n) {
                if (qmin.isEmpty() || qmin.peekLast() != j) {
                    // 动态更新最小值
                    while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[j]) {
                        qmin.pollLast();
                    }
                    qmin.offerLast(j);

                    // 动态更新最大值
                    while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[j]) {
                        qmax.pollLast();
                    }
                    qmax.offerLast(j);
                }

                // 当前 arr[j] 加入后，将破坏 最大值与最小值的范围
                if (arr[qmax.getFirst()] - arr[qmin.getFirst()] > num) {
                    break;
                }
                j++;
            }
            ans += (j - i);

            if (qmin.peekFirst() == i) {
                qmin.pollFirst();
            }

            if (qmax.peekFirst() == i) {
                qmax.pollFirst();
            }
            i++;
        }

        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Main().numOfRangeSubArr(new int[]{2,1,3,4,5}, 2));
    }
}
